package com.github.hgkmail.hello.leetcode101.base;

import java.util.HashMap;
import java.util.Map;

//使用HashMap实现的并查集
//数组实现局限性有点大，要求：非负（下标最小是0）、数字不能太大（内存会溢出）
public class UnionFindWithMap {
    //父坐标
    public Map<Integer, Integer> parent;
    //树的大小
    public Map<Integer, Integer> size;
    //初始化
    public UnionFindWithMap(int[] array) {
        parent = new HashMap<>(array.length);
        size = new HashMap<>(array.length);
        for (int i = 0; i < array.length; i++) {
            parent.put(array[i], array[i]);
            size.put(array[i], 1);
        }
    }
    //迭代查找根坐标(推荐，够简洁)
    public int find(int i) {
        while (parent.get(i)!=i) {
            //路径压缩，把i挂到爷爷节点
            parent.put(i, parent.get(parent.get(i)));
            i=parent.get(i);
        }
        return i;
    }
    //是否相连（根坐标是否相同）
    //可用于判断无向图是否有回路：将一条边加入UF前，判断2个节点是否相连，如果相连，那么加入这条边后必定成回路
    public boolean isConnected(int i, int j) {
        return find(i)==find(j);
    }
    //合并
    public void union(int i, int j) {
        int rootI=find(i);
        int rootJ=find(j);
        if (rootI==rootJ) {
            return;
        }
        //把小的挂在大的下面
        if (size.get(rootI)>=size.get(rootJ)) {
            parent.put(rootJ, rootI);
            size.put(rootI, size.get(rootI)+size.get(rootJ));
        } else {
            parent.put(rootI, rootJ);
            size.put(rootJ, size.get(rootI)+size.get(rootJ));
        }
    }

    //测试
    public static void main(String[] args) {
        UnionFindWithMap uf = new UnionFindWithMap(new int[]{0,1,2,3,4});
        uf.union(0,1); //分量1
        uf.union(2,3); //分量2
        System.out.println(uf.isConnected(0,2));
        uf.union(1,4);
        uf.union(3,4);
        System.out.println(uf.isConnected(0,2));
    }
}
